package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;



import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.TreeNode;

/*
 * 
原题　
	Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
	
	According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
	
	        _______6______
	       /              \
	    ___2__          ___8__
	   /      \        /      \
	   0      _4       7       9
	         /  \
	         3   5
	For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
题目大意
	给定二叉搜索树（BST），找到BST中两个给定节点的最低共同祖先（LCA）。
	
	根据维基百科的LCA的定义：“最小的共同祖先在两个节点v和w之间定义为T中具有v和w作为后代的最低节点（我们允许一个节点为自己的后代）。 ”
	
       _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
	例如，节点2和8的最低共同祖先（LCA）为6.另一个例子是节点2和节点4的LCA为2，因为根据LCA定义，节点可以是其自身的后代。
解题思路
	如果如果p,q 比root小, 则LCA必定在左子树, 如果p,q比root大, 则LCA必定在右子树. 如果一大一小, 则root即为LCA.
 * @Date 2017-09-18 21：28
 */
public class _235_Lowest_Common_Ancestor_of_a_Binary_Search_Tree {
	
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    	if (root==null || p==null || q==null)	return null;
    	if (Math.max(p.val, q.val) > root.val)		return lowestCommonAncestor(root.right, p, q);	//max
    	else if (Math.min(p.val, q.val) < root.val)	return lowestCommonAncestor(root.left,  p, q);	//min
    	else return root;
    }
	
	public void traverse(int[] nums) {
		for (int i : nums) {
			LogUtils.print(i);
		}
	}
//	
//	private TreeNode newTree1() {
//		return new TreeNode(5, 
//					new TreeNode(2, 
//							new TreeNode(3, null, 
//									new TreeNode(4)
//							), null 
//					), 
//					new TreeNode(2, 
//							null, 	new TreeNode(3, new TreeNode(4), null)
//					)
//				);
//	}
    
	public static void main(String[] args) {
		_235_Lowest_Common_Ancestor_of_a_Binary_Search_Tree obj = new _235_Lowest_Common_Ancestor_of_a_Binary_Search_Tree();

		obj.lowestCommonAncestor(null, null, null);
	}

}
